package leetcode_700;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *DegreeOfAnArray_697 一个数组的度是数组出现元素频率最高的次数 那么求这个数组最短子数组拥有相同度的长度
 *describe:用map记录频率 list记录候选解 遍历即可 AC 41%
 *2018年10月10日 上午9:27:29
 */
public class DegreeOfAnArray_697 {
	public int findShortestSubArray(int[] nums) {
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();//候选map 记录所有数的频率
        List<Integer> index=new ArrayList<Integer>();//记录最大的那些候选值
        int max=0;
        for(int i:nums) {
        	int count=map.getOrDefault(i, 0)+1;
        	map.put(i, count);
        	if(count>max) {//候选值发生了变化
        		max=count;
        		index.clear();//清空原有数据
        		index.add(i);
        	}
        	else if(count==max) {//有相同解
        		index.add(i);
        	}
        }
        if(max==1)//所有数都只出现1次
        	return 1;
        int min=nums.length;
        for(int i:index) {//依次取出候选值 其实候选值不会太多
        	int left=0,right=nums.length-1;
        	while(nums[left]!=i)
        		++left;
        	while(nums[right]!=i)
        		--right;
        	min=Math.min(min, right-left+1);
        }
        return min;
    }
}
